// #include <stdio.h>
// #include <stdbool.h>
// #include <limits.h>
// #include <stdlib.h>
// #include <time.h>
//
// #include "windows.h"
//
// typedef int DataType;
//
// typedef struct TreeNode {
//     DataType value;
//     struct TreeNode* left;
//     struct TreeNode* right;
// } TreeNode;
//
// // 队列节点结构
// typedef struct QueueNode {
//     TreeNode* data; // 存储数据
//     struct QueueNode* next; // 指向下一个节点
// } QueueNode;
//
// // 队列结构
// typedef struct {
//     QueueNode* front; // 队头指针
//     QueueNode* rear;  // 队尾指针
// } LinkQueue;
//
// void InitQueue(LinkQueue* q) {
//     q->front=q->rear=NULL;
// }
//
// void Enqueue(LinkQueue* q,TreeNode* x){
//     QueueNode* newNode=(QueueNode*)malloc(sizeof(QueueNode));
//     if(newNode==NULL) {
//         exit(1);
//     }
//     newNode->data=x;
//     newNode->next=NULL;
//
//     if(q->front==NULL&&q->rear==NULL) {
//         q->front=q->rear=newNode;
//     }else {
//         q->rear->next=newNode;
//         q->rear=q->rear->next;
//     }
// }
//
// TreeNode* Dequeue(LinkQueue* q) {
//     if(q->front==NULL) {
//         return NULL;
//     }
//     QueueNode* tmp=q->front;
//     q->front=q->front->next;
//     TreeNode* node=tmp->data;
//     if(q->front==NULL) {
//         q->rear=NULL;//必须要这步
//     }
//     free(tmp);
//     return node;
// }
//
// // 创建新节点
// TreeNode* ChaRuElem(DataType value) {
//     TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
//     if (newNode == NULL) {
//         exit(0);
//     }
//     newNode->value = value;
//     newNode->right = newNode->left = NULL;
//     return newNode;
// }
//
// // 插入节点
// TreeNode* ChaRuNode(TreeNode* root, DataType value) {
//     if (root == NULL) {
//         return ChaRuElem(value);
//     }
//     if (value < root->value) {
//         root->left = ChaRuNode(root->left, value);
//     } else {
//         root->right = ChaRuNode(root->right, value);
//     }
//     return root;
// }
//
// //先序
// void PrePrint(TreeNode* root) {
//     if(root) {
//         printf("%d ",root->value);
//         PrePrint(root->left);
//         PrePrint(root->right);
//     }
// }
//
// void FreeTree(TreeNode* root) {
//     if(root) {
//         FreeTree(root->left);
//         FreeTree(root->right);
//         free(root);
//     }
// }
//
// int MaxH(DataType a,DataType b) {
//     if(a>b) {
//         return a;
//     }else {
//         return b;
//     }
// }
//
// //树高(递归)
// int TreeHDiGui(TreeNode* root) {
//     if(root==NULL) {
//         return 0;
//     }else {
//         return MaxH(TreeHDiGui(root->left),TreeHDiGui(root->right))+1;
//     }
// }
//
// //当前队列元素个数
// int QueueLength(LinkQueue* q) {
//     if(q==NULL) {
//         exit(1);
//     }
//     QueueNode* p=q->front;
//     int count=0;
//     while (p!=NULL) {
//         count++;
//         p=p->next;
//     }
//     return count;
// }
//
// //求树高
// int LeverOrderTreeH(TreeNode* root) {
//     if(root==NULL) {
//         return 0;
//     }
//     int h=0;
//     LinkQueue q;
//     InitQueue(&q);
//     Enqueue(&q,root);
//     while (q.front!=NULL) {
//         int count=0;
//         count=QueueLength(&q);
//         h++;
//         while (count>0) {
//             TreeNode* p=Dequeue(&q);
//             if(p->left)Enqueue(&q,p->left);
//             if(p->right)Enqueue(&q,p->right);
//             count--;
//         }
//     }
//     return h;
// }
//
// int main() {
//     SetConsoleOutputCP(CP_UTF8);
//     TreeNode* root=NULL;
//     int value[]={50,40,30,20,60,70,80};
//     int length=sizeof(value)/sizeof(value[0]);
//     for(int i=0;i<length;i++) {
//         root=ChaRuNode(root,value[i]);
//     }
//     int result1=LeverOrderTreeH(root);
//     printf("树高为:%d\n",result1);
//     int result2=TreeHDiGui(root);
//     printf("递归树高为:%d\n",result2);
//
//     FreeTree(root);
//     return 0;
// }